package leetcode;
import java.util.*;
public class LeetCodeMain123 {
    public int openLock(String[] deadends, String target) {
        Set<String> set=new HashSet<>();
        for (String str:deadends) {
            set.add(str);
        }
        Set<String> book=new HashSet<>();
        Queue<String> q=new LinkedList<>();
        if (set.contains("0000")){
            return -1;
        }
        q.add("0000");
        book.add("0000");
        int step=0;
        while (!q.isEmpty()){
            int size=q.size();
            while (size>0){
                size--;
                String s=q.poll();
                if (s.equals(target)){
                    return step;
                }
                for (int i = 0; i < s.length(); i++) {
                    char ch1=s.charAt(i);
                    char ch2=s.charAt(i);
                    if (ch1=='9'){
                        ch1='0';
                    }else {
                        ch1++;
                    }
                    if (ch2=='0'){
                        ch2='9';
                    }else {
                        ch2--;
                    }
                    StringBuilder sb1=new StringBuilder(s);
                    StringBuilder sb2=new StringBuilder(s);
                    sb1.setCharAt(i,ch1);
                    sb2.setCharAt(i,ch2);
                    if (!set.contains(sb1.toString())&&!book.contains(sb1.toString())){
                        q.offer(sb1.toString());
                        book.add(sb1.toString());
                    }
                    if (!set.contains(sb2.toString())&&!book.contains(sb2.toString())){
                        q.offer(sb2.toString());
                        book.add(sb2.toString());
                    }
                }
            }step++;
        }
        return -1;
    }

}
